#include <stdio.h>
#include <stdlib.h>

#define MAX_NUM 100
#define FLAG -100

typedef int Datatype;
typedef enum bool Bool;
enum bool {
        false, true
};

struct Node {
        Datatype val;
        struct Node *next;
};
typedef struct Node *PNode;
typedef struct Node *LinkList;

struct LinkStack {
        LinkList top;
        int len;
        int MAXNUM;
};
typedef struct LinkStack *PLinkStack;

PLinkStack createEmptyStack_link(void);
Bool isEmptyStack_link(PLinkStack plstack);
Bool Stack_is_full(PLinkStack plstack);
void push_link(PLinkStack plstack, Datatype x);
void pop_link(PLinkStack plstack);
Datatype top_link(PLinkStack plstack);

// 注意：我们的链栈没有头结点.
PLinkStack createEmptyStack_link(void)
{
        PLinkStack plstack = (PLinkStack)malloc(sizeof(struct LinkStack));
        plstack->top = NULL;
        plstack->len = 0;
        plstack->MAXNUM = MAX_NUM;
        return plstack;
}

Bool isEmptyStack_link(PLinkStack plstack)
{
        return plstack->top     == NULL;
}

Bool Stack_is_full(PLinkStack plstack)
{
        return plstack->len >= plstack->MAXNUM;
}

// 在栈顶头结点下面开始插入元素.
void push_link(PLinkStack plstack, Datatype x)
{
        // 入栈，首先判断栈是否满.
        if (Stack_is_full(plstack)) {
                printf("The Stack is full! Can't push element now!\n");
                return ;
        }
        // 不满就开辟新结点，插入之.
        PNode p = (PNode)malloc(sizeof(struct Node));
        p->val = x;
        // 先立新，再破旧.
        p->next = plstack->top;
        plstack->top = p;
}

Datatype top_link(PLinkStack plstack)
{
        if (!plstack->top) return -100;
        return plstack->top->val;
}

// 虽然进行了pop操作，但top指针依然指向链表的第一个元素，因为我们采用的是 头插法和头删法.
void pop_link(PLinkStack plstack)
{
        if (isEmptyStack_link(plstack)) {
                printf("Now the stack is empty! Can't pop!\n");
                return ;
        }
        plstack->top = plstack->top->next;
}

PLinkStack createLinkStack_H(void)
{
        PLinkStack S = createEmptyStack_link();
        int x, tmp = 0;
        scanf("%d", &x);
        while (x != FLAG) {
                PNode p = (PNode)malloc(sizeof(struct Node));
                p->val = x;
                tmp++;
                p->next = S->top;
                S->top = p;
                scanf("%d", &x);
        }
        S->len = tmp;
        return S;
}

void print_Stack(PLinkStack S)
{
        if (isEmptyStack_link(S)) {
                printf("Now the stack is empty!\n");
                return ;
        }
        PNode p;
        for (p = S->top; p != NULL; p = p->next) {
                printf("%d ", p->val);
        }
        printf("\n");
}

int main()
{
        PLinkStack S = createLinkStack_H();
        print_Stack(S);
        if (isEmptyStack_link(S)) {
                printf("The stack is empty!\n");
        } else {
                printf("The stack is not empty\n");
        }
        if (Stack_is_full(S)) {
                printf("The stack is full!\n");
        } else {
                printf("The stack is not full!\n");
        }
        int x;
        printf("Please input a number to push:");
        scanf("%d", &x);
        push_link(S, x);
        print_Stack(S);
        pop_link(S);
        print_Stack(S);
        printf("The stack's top element is %d\n", top_link(S));
        return 0;
}
